Network devices, such as network switches, bridges, routers, edge devices and the like, often employ lookup tables that store various types of information associated with packets processed by the network devices. The network devices often perform searches/lookups in the lookup tables to make various processing decisions or determinations (e.g., a classification for a packet, a port to which the packet is to be forwarded, etc.) when processing the packets. In general, a lookup for a packet is performed according to a key associated with the packet. The key typically includes information from a header of the packet and at times other information that may not be included in the header, such as an ingress interface. The key is used to search a table, for example, and information relevant to the packet (e.g., forwarding information for the packet, or information indicative of some other action) is retrieved from a table entry that is identified by the key.
Some lookup tables are implemented using content addressable memory (CAM) (e.g., ternary CAM (TCAM)), which is commonly used for “masked” searches/lookups. In recent years, however, network devices have increasingly begun to perform “exact match” lookups. While CAM based tables may be used for exact match lookups, they are generally less efficient for such lookups (e.g., in terms of area and power consumption) than random access memory (RAM) based tables, such as tables implemented using static RAM (SRAM). Exact match lookups are currently used to perform any of numerous different packet processing operations, such as packet classifications, making forwarding or routing decisions, quality of service classifications, policy control list applications, tunnel termination operations, etc. Moreover, due to the wide variety of possible processing operations, exact match lookups can require using a number of different types of keys having different key sizes. Typically, for example, bridging lookups based on a medium access control (MAC) address and virtual local area network (VLAN) identifier use a 60 bit key, forwarding and/or classification lookups based on a double VLAN tag use a 24 bit key, lookups for routing to IPv4 addresses use a 32 bit key, lookups for routing to IPv6 addresses use a 128 bit key, and so forth. To handle the various key sizes, some conventional network devices either pad all shorter keys to the bit length of the largest supported key size, or provide separate lookup tables stored in different memories, with each table being indexed only by keys of a single, fixed size. Both techniques, however, are generally inefficient with respect to utilization of memory resources, which can ultimately increase circuit area and/or power consumption. With respect to the former technique, for example, even relatively short keys occupy the same amount of lookup table memory as a long key. Moreover, because the number of entries that will be required for each table/key size, and/or the distribution of key sizes, is typically not known a priori, a system designer using the latter technique is generally unable to determine the amount of entries per lookup table/key size that will efficiently utilize lookup memory resources.